import java.util.Stack;

//TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or
// click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.
public class Main {
    //1.括号匹配
    Stack<Character> stack = new Stack<>();
    public boolean isValid(String s) {
        int len = s.length();
        // 遍历字符串;
        for (int i = 0; i < len; i++) {
            char ch = s.charAt(i);
            // 遇到左括号就压入栈中;
            if (ch == '{' || ch == '[' || ch == '(') {
                stack.push(ch);
            } else {
                // 遇到右括号，判断栈中是否为空，为空则直接返回false，不为空则弹出元素;
                if (!stack.isEmpty()) {
                    char ch1 = stack.pop();
                    // 将弹出的元素与字符串中的右括号匹配;
                    if (!isMatch(ch, ch1)) {
                        return false;
                    }
                } else {
                    return false;
                }
            }
        }
        // 当s遍历完之后，stack不为空，则返回false;
        if (!stack.isEmpty()) {
            return false;
        }
        // 其余的情况就是ture;
        return true;
    }

    private boolean isMatch(char ch1, char ch) {
        if (ch == '{' && ch1 == '}' || ch == '[' && ch1 == ']' || ch == '(' && ch1 == ')') {
            return true;
        } else {
            return false;
        }
    }
    //2.逆波兰表达式求值
    Stack<Integer> stack = new Stack<>();
    public int evalRPN(String[] tokens) {
        // 遍历tokens将数字放入stack中;
        int len = tokens.length;
        for (int i = 0; i < len; i++) {
            String str = tokens[i];
            // 判断str是否为运算符，不是运算符则放入stack中;
            if (!isOperator(str)) {
                // str不是运算符;
                int ret = Integer.valueOf(str);
                stack.push(ret);
            } else {
                // str为运算符,弹出stack中两个数字
                int rightNum = stack.pop();
                int leftNum = stack.pop();
                // 弹出元素进行运算,并将计算的结果放入stack中;
                switch (str) {
                    case "+":
                        stack.push(leftNum + rightNum);
                        break;
                    case "-":
                        stack.push(leftNum - rightNum);
                        break;
                    case "*":
                        stack.push(leftNum * rightNum);
                        break;
                    case "/":
                        stack.push(leftNum / rightNum);
                        break;
                }
            }
        }
        return stack.pop();
    }

    private boolean isOperator(String str) {
        if (str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/")) {
            return true;
        }
        return false;
    }
    //3.出栈入栈次序匹配
    Stack<Integer> stack = new Stack<>();
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        int j = 0;
        //1.压栈
        for(int i = 0;i < pushV.length;i++) {
            stack.push(pushV[i]);
            //2.比较popV元素是否与栈顶元素相同
            while(j < popV.length &&  !stack.isEmpty() && popV[j] == stack.peek()) {
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }
    //4.最小栈
    Stack<Integer> stack = new Stack<>();
    Stack<Integer> minStack = new Stack<>();

    public MinStack() {
    }

    public void push(int val) {
        // 1.minStack为空
        if (minStack.isEmpty()) {
            minStack.push(val);
        } else {
            // 2.minStack不为空，则比较，小于等于minStac栈顶的元素则压栈，反之则不压栈
            int tmp = minStack.peek();
            if (tmp >= val) {
                minStack.push(val);
            }
        }
        stack.push(val);
    }

    public void pop() {
        // 1.判断stack与minStack栈顶元素是否相同
        // 2.相同则一起弹出，反之stack弹出，minStack不弹出
        int ret = stack.pop();
        if (ret == minStack.peek()) {
            minStack.pop();
        }

    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
    public static void main(String[] args) {

    }
}